3981. От матрицы смежности к спискам смежности

Простой ориентированный граф задан матрицей смежности. Выведите его представление в виде списков смежности.

Вход. В первой строке находится количество вершин графа n (1 ≤ n ≤ 100). Во второй строке и далее – матрица смежности. Гарантируется, что граф не содержит петель.

Выход.  Выведите n строк – списки смежности графа. В i-ой строке сначала выведите количество исходящих из i-ой вершины рёбер, а затем – номера вершин, в которые эти рёбра входят, упорядоченные по возрастанию.

Пример входа	Пример выхода
5 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0	1 3 2 1 3 1 5 2 1 2 2 1 2

РЕШЕНИЕ

графы

Анализ алгоритма

Читаем матрицу смежности, строим список смежности. После чего выводим его.

Пример

Граф из примера имеет следующий вид.

Реализация алгоритма

Объявим список смежности графа.

vector<vector<int> > g;

Читаем входные данные. Вершины нумеруются с 1 до n. Строим список смежности графа.

scanf("%d", &n);

g.resize(n + 1);

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)

{

scanf("%d", &val);

if (val) g[i].push_back(j);

}

Выводим список смежности.

for (i = 1; i <= n; i++)

{

printf("%d", g[i].size());

for (j = 0; j < g[i].size(); j++)

printf(" %d", g[i][j]);

printf("\n");

}

Java реализация – array of ArrayList

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

ArrayList<Integer>[] g = new ArrayList[n+1]; // unchecked

for (int i = 0; i <= n; i++)

g[i] = new ArrayList<Integer>();

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

{

int val = con.nextInt();

if (val == 1) g[i].add(j);

}

for(int i = 1; i <= n; i++)

{

System.out.print(g[i].size());

for(int j = 0; j < g[i].size(); j++)

System.out.print(" " + g[i].get(j));

System.out.println();

}

con.close();

}

}

Java реализация – ArrayList of ArrayList

import java.util.*;

import java.io.*;

public class Main

{

public static void main(String[] args) throws IOException

{

//Scanner con = new Scanner(new FileReader ("3981.in"));

Scanner con = new Scanner(System.in);

int n = con.nextInt();

ArrayList<ArrayList<Integer>> g =

new ArrayList<ArrayList<Integer>>();

for (int i = 0; i <= n; i++)

g.add(new ArrayList<Integer>());

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

{

int val = con.nextInt();

if (val == 1) g.get(i).add(j);

}

//System.out.println(g);

for(int i = 1; i <= n; i++)

{

System.out.print(g.get(i).size());

for(int j = 0; j < g.get(i).size(); j++)

System.out.print(" " + g.get(i).get(j));

System.out.println();

}

con.close();

}

}